package com.example.array;

public class Leetcode922_SortArrayByParityII {
    public static void main(String[] args) {
        int[] res = sortArrayByParityII2(new int[]{5, 6, 4, 2, 3, 7});
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + ", ");
        }

    }

    public static int[] sortArrayByParityII(int[] nums) {
        int[] result = new int[nums.length];
        // 定义两个指针分别指向结果数组的奇偶子组下标
        int even = 0;
        int odd = 1;
        // 遍历nums当nums[i]为奇将值赋给结果奇子组，当nums[i]为偶将值赋给结果偶子组
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                result[even] = nums[i];
                even += 2;
            } else {
                result[odd] = nums[i];
                odd += 2;
            }
        }
        return result;
    }

    /**
     * 为数组的偶数下标部分和奇数下标部分分别维护指针 i,j。
     * 遍历数组
     * 如果 A[i]为奇数，则不断地向前移动j（每次移动两个单位），直到遇见下一个偶数。
     * 此时，可以直接将 A[i]与 A[j]交换。
     *
     * @param nums
     * @return
     */
    public static int[] sortArrayByParityII2(int[] nums) {
        int odd = 1;
        int even = 0;
        while (even < nums.length) {
            if (nums[even] % 2 == 1) {
                while (nums[odd] % 2 == 1) {
                    odd += 2;
                }
                swap(nums, even, odd);
            }

            even += 2;
        }
        return nums;
    }

    public static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
